Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 6
на тему:
"Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ"
з дисципліни:
" Програмування. Частина III. Структури даних та алгоритми "
Львів – 2013
Мета роботи:
Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач.
Постановка задачі:
І. Завдання 1: Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати:
послідовність вершин дерева при проходженні його у прямому порядку;
послідовність листків дерева при проходженні його у зворотньому порядку;
послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.
Виконати індивідуальне завдання згідно з варіантом.
Знайти середнє арифметичне значення всіх листків дерева.
ІІ. Завдання 2: Використовуючи побудоване в Завданні 1 бінарне дерево пошуку, розв'язати задачу згідно з варіантом.
Варіанти завдань:
1. Операційні системи типу UNIX, PC-DOS (старші версії) підтримують деревоподібну структуру збереження даних на диску. При цьому мінімальна іменована одиниця інформації називається файлом. Файли об'єднуються в каталоги, кожний з яких теж має ім'я. Множина каталогів і окремих файлів можуть у свою чергу також утворити каталог більш високого рівня. Каталог найвищого рівня називається кореневим. Кількість рівнів вкладеності не обмежена. Розглядати тільки випадки без порожніх каталогів (тобто каталогів, що не мають файлів).
Скласти програму для виводу на екран по рівнях:
а) списку всіх елементів даних, "вкладених" у довільний каталог на всіх рівнях;
б) списку всіх каталогів, "вкладених" у довільний каталог;
в) списку всіх файлів, "вкладених" у довільний каталог;
г) списку всіх елементів даних кореневого каталогу, виведених в алфавітному порядку.
Приклад:
На заданій схемі елемент 0 є кореневим каталогом диску;
елементи 2,3,6,10 - каталогами; елементи 1,4,7,9,8,5 - файлами.
Для каталогу 2 перше завдання має виводити таку
послідовність:
2
6
4
7
9
Алгоритм розв’язання:
Код програми:
І. Завдання 1
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct node
{
int data;
struct node *leftson, *rightson;
}
*binary_tree;
void Init(binary_tree *root_ptr);
int Empty(binary_tree root);
binary_tree WhoRight(binary_tree tree_node);
void PutLeftLeft(binary_tree tree_node);
binary_tree Who(binary_tree root, int new_data);
void PutRight(binary_tree root, int new_data);
binary_tree Find(binary_tree root, int search_data);
int GoStraight(binary_tree root,int k,int z);
void GoSymmetric(binary_tree root);
void GoReverse(binary_tree root);
int Compare(binary_tree root1,binary_tree root2);
binary_tree WhoFather(binary_tree root, binary_tree knot);
binary_tree WhoBrother(binary_tree root, binary_tree knot);
void AddSearchTree(binary_tree *root_ptr, int new_data);
void DeleteSearchTree(binary_tree *root_ptr, int del_data);
void PrintLevel(binary_tree root, int k, int i);
void PrintTurningTree(binary_tree root, int h);
int kil=0;
int mas1[100],i=0;
void main()
{
int z,k=0;
double ser=0;
binary_tree t1,p ;
int x;
unsigned i,n;
Init(&t1);
printf("Enter the number of knots of binary tree 1: ");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&x);
AddSearchTree(&t1, x);
};
printf("\n");
kil=0;
k=GoStraight(t1,k,0); //kilkist vyzliv pru priamomy prohodgenni
printf("\nkilkist vyzliv=%d",kil);
printf("\n");
kil=0;
GoSymmetric(t1); //kilkist vyzliv z 1 nashcadkom pru symetru4nomy
z=kil;
printf("\nkilkist vyzliv z 1 nashcadkom=%d",z);
printf("\n");
kil=0; i=0;
GoReverse(t1); //kilkist lustkiv pru z...
